computervisionfandomcom-20200214-history
Edge detection
NOTE! The text on edge detection in the regular Wikipedia is much better than this text! The goal of edge detection is to mark the points in an image at which the intensity changes sharply. Sharp changes in image properties usually reflect important events and changes in world properties. Edge detection is a research field within Computer vision and Feature extraction. Edge properties Edges may be viewpoint dependent - these are edges that may change as the viewpoint changes, and typically reflect the geometry of the scene, objects occluding one another and so on, or may be viewpoint independent - these generally reflect properties of the viewed objects such as markings and surface shape. In two dimensions, and higher, the concept of a projection has to be considered. A typical edge might be (for instance) the border between a block of red color and a block of yellow; in contrast a line can be a small number of pixels of a different color on an otherwise unchanging background. There will be one edge on each side of the line. Detecting an edge Taking an edge to be a change in intensity taking place over a number of pixels, edge detection algorithms generally calculate a derivative of this intensity change. To simplify matters, we can consider the detection of an edge in 1 dimension. In this instance, our data can be a single line of pixel intensities. For instance an edge can clearly be detected between the 4th and 5th pixels in the following 1-dimensional data: 5 7 6 4 153 148 149 Calculating the 1st derivative Many edge-detection operators are based upon the 1st derivative of the intensity - this gives us the intensity gradient of the original data. Using this information we can search an image for peaks in the intensity gradient. If I(x) represents the intensity of pixel x, and I'(x) represents the first derivative (intensity gradient) at pixel x, the central difference operator can be used: I'(x) = -1.I(x-1) + 0.I(x) + 1.I(x+1) Tthe 1st derivative can therefore be estimated (in 1D) by convolving the original data with a mask: -1 0 1 This central difference operator yields an estimate of the derivative that is on the same data lattice as the original intensity values, but has only half the resolution. This can be partly improved on, in two dimensions, by using the Roberts-cross operator. Full resolution is achieved using the Costella gradient operator. Calculating the 2nd derivative Some other edge-detection operators are based upon the 2nd derivative of the intensity. This is essentially the rate of change in intensity gradient and is best at detecting lines :- as noted above, a line is a double edge, hence we will see an intensity gradient on one side of the line, followed immediately by the opposite gradient on the opposite site. Therefore we can expect to see a very high change in intensity gradient where a line is present in the image. To find lines, we can search the results for zero-crossings of the change in gradient. If I(x) represents the intensity at point x, and I"(x) is the second derivative at point x: I"(x) = 1.I(x-1) - 2.I(x) + 1.I(x+1) Again most algorithms use a convolution mask to quickly process the image data: +1 -2 +1 Thresholding Once we have calculated our derivative, the next stage is to apply a threshold, to determine where the results suggest an edge is present. The lower the threshold, the more lines will be detected, and the results become increasingly susceptible to noise, and also to picking out irrelevant features from the image. Conversely a high threshold may miss subtle lines, or sections of lines. A commonly used compromise is thresholding with hysteresis. This method uses multiple thresholds to find edges. We begin by using the upper threshold to find the start of a line. Once we have a start point, we trace the edge's path through the image pixel by pixel, marking an edge whenever we are above the lower threshold. We stop marking our edge only when the value falls below our lower threshold. This approach makes the assumption that edges are likely to be in continuous lines, and allows us to follow a faint section of an edge we have previously seen, without meaning that every noisy pixel in the image is marked down as an edge. Edge detection operators * 1st order: Costella, Roberts-cross, Prewitt, Sobel, Canny, Spacek * 2nd Order: Laplacian, Marr-Hildreth Currently, the Canny operator is most commonly used, followed by Marr-Hildreth. Very many operators have been published but so far none have any significant advantage over the Canny operator in general situations. Work on multi-scale techniques is still very much in the labs. Further reading Rafael Grompone von Gioi; Jeremie Jakubowicz; Jean-Michel Morel; Gregory Randall. "LSD: a Line Segment Detector". LSD detects line segments with subpixel accurate results. ANSI C source code available. Category:Techniques